📦 gopikrishna000 / templates-latest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49<snippet>
	<content><![CDATA[


const int K = 25;
const int MAXN = 5e5 + 7;
int lg[MAXN + 1];
int st1[K + 1][MAXN];
int st2[K + 1][MAXN];


int rmin(int L, int R) {
	int j = lg[R - L + 1];
	return min(st1[j][L], st1[j][R - (1 << j) + 1]);
}

int rmax(int L, int R) {
	int j = lg[R - L + 1];
	return max(st2[j][L], st2[j][R - (1 << j) + 1]);
}

void sparse_table(vector<int> &arr) {
    int n = arr.size();
	lg[1] = 0;
	for (int i = 2; i <= MAXN; i++)
		lg[i] = lg[i / 2] + 1;

	std::copy(arr.begin(), arr.end(), st1[0]);
	std::copy(arr.begin(), arr.end(), st2[0]);

	for (int j = 1; j <= K; j++)
		for (int i = 0; i + (1 << j) <= n; i++)
			st1[j][i] = min(st1[j - 1][i], st1[j - 1][i + (1 << (j - 1))]);


	for (int j = 1; j <= K; j++)
		for (int i = 0; i + (1 << j) <= n; i++)
			st2[j][i] = max(st2[j - 1][i], st2[j - 1][i + (1 << (j - 1))]);
}



]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>sparse table</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<scope>source.c++</scope>
</snippet>